Contents

1. 1. 题意
2. 2. 分析：

题意

　　给定一序列的单词按照字典序输入，要求某些单词是由这其中的其它两个单词拼接而成的单词按照字典序输出

分析：

　　把输入的单词建一棵字典树，然后每单单词拆成两半去字典树里找

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 50010;
const int N = 150;//单词最大长度
const int M = 26;

struct Node{
    int mark;
    Node *childs[M];
};

Node node[MAXN * N];
Node *root;
int pos, numWord;
char word[MAXN][N];

Node *newnode(){
    node[pos].mark = 0;
    for(int i = 0; i < M; i++){
        node[pos].childs[i] = NULL;
    }
    return &node[pos++];
}

void Insert(char *str){

    int len = strlen(str);
    Node *s = root;
    for(int i = 0; i < len; i++){
        int index = str[i] - 'a';
        if(s->childs[index] == NULL)
            s->childs[index] = newnode();
        s = s->childs[index];
    }
    s->mark = 1;
}

bool Search(char *str){

    Node *s = root;
    int len = strlen(str);
    for(int i = 0; i < len; i++){
        int index = str[i] - 'a';
        if(s->childs[index] == NULL)
            return false;
        s = s->childs[index];
    }
    return s->mark == 1; //判断找到这个字母(str最后一个字母)时，str字典树中是否是一个单词
}

void solve(){

    for(int i = 0; i < numWord; i++){
        int len = strlen(word[i]);
        for(int j = 1; j < len; j++){
            char temp[N];
            strcpy(temp, word[i]);
            temp[j] = '\0';//注意要有这句
            if(Search(temp) && Search(word[i] + j)){
                printf("%s\n", word[i]);
                break;
            }
        }
    }
}

int main(){

    numWord = 0;
    pos = 0;
    root = newnode();
    while(scanf("%s", word[numWord]) != EOF){
        Insert(word[numWord++]);
    }
    solve();
    return 0;
}